#include "headfiles.h"

using namespace std;

// create a min-heap. starting from the last element
//
bool createHeap(int *array, int n) {
    if (array == NULL||
        n <= 0) {
        cout << "Invalid input arguments!" << endl;
        return false;
    }

    int i, parent_index, index;
    int end_index = 1;
    for (i = end_index; i < n; i++) {
        index = i;
        parent_index = (index - 1) / 2;
        while (parent_index >= 0) {
            if (array[index] < array[parent_index]) {
                int tmp = array[index];
                array[index] = array[parent_index];
                array[parent_index] = tmp;
            }

            if (parent_index == 0) {
                break;
            }

            index = parent_index;
            parent_index = (index - 1) / 2;
        }
    }

    return true;
}

static bool replaceMinElement(int *array, int n, int e) {
    if (array == NULL ||
        n <= 0) {
        cout << "Invalid input argument!" << endl;
        return false;
    }

    if (e <= array[0]) {
        return true;
    }

    array[0] = e;

    int index, l_index, r_index, chosen_index;
    index = 0;
    while (index < n) {
        l_index = 2 * index + 1;
        r_index = 2 * index + 2;
        chosen_index = -1;
        if (l_index < n && array[index] > array[l_index]) {
            chosen_index = l_index;
        }

        if (r_index < n && array[index] > array[r_index]) {
            if (array[l_index] > array[r_index]) {
                chosen_index = r_index;
            }
        }

        if (chosen_index != -1) {
            int tmp = array[chosen_index];
            array[chosen_index] = array[index];
            array[index] = tmp;

            index = chosen_index;
        }
        else {
            break;
        }
    }

    return true;
}

bool findnNums(int *array, int n, int m) {
    if (array == NULL||
        n <= 0 ||
        m > n) {
        cout << "Invalid input arguments!" << endl;
        return false;
    }

    // Create a min heap with the first m elements
    bool ret;
    ret = createHeap(array, m);
    if (ret == false) {
        cout << "Create heap error!" << endl;
        return false;
    }

    int i;
    for (i = m; i < n; i++) {
        ret = replaceMinElement(array, m, array[i]);
        if (ret == false) {
            cout << "Replace element array[" << i << "] = " << array[i] << " error!" << endl;
            return false;
        }
    }

    cout << "The biggest " << m << " elements are:" << endl;
    for (i = 0; i < m; i++) {
        cout << array[i] << endl;
    }

    return true;
}

bool findnNums1(int *array, int n, int m) {
    if (array == NULL||
        n <= 0 ||
        m > n) {
        cout << "Incorrect input arguments!" << endl;
        return false;
    }

    srand(time(NULL));

    int start = 0;
    int end = n;
    int l, r, index;
    int pivot_loc, pivot;

    int round = 0;
    while (true) {
        cout << "round = " << round << ", start = " << start << ", end = " << end << "." << endl;
        l = start + 1;
        index = start;
        r = end - 1;
        pivot_loc = rand() % (end - start) + start;
        pivot = array[pivot_loc];
        array[pivot_loc] = array[start];

        while (l <= r) {
            if (array[l] >= pivot) {
                array[index] = array[l];
                index++;
                l++;
            }
            else {
                // swap l with the last element
                int tmp = array[l];
                array[l] = array[r];
                array[r] = tmp;
                r--;
            }
        }
        array[index] = pivot;

        if (index == m) {
            //Print out the elements from 0 to index-1
            break;
        }
        else if (index == m - 1) {
            //Print out the elements from 0 to index
            ++index;
            break;
        }
        else if (index > m) {
            end = index;
        }
        // index < m - 1
        else {
            start = index + 1;
        }
    }
        
    int i;
    cout << "Founded elements are:" << endl;
    for (i = 0; i < index; i++) {
        cout << array[i] << endl;
    }

    return true;
}


